package com.atguigui.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 面试题 04.06SuccessorLcci
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/5/16 8:35
 */
public class SuccessorLcci {
    public static void main(String[] args) {
        Solution solution = new SuccessorLcci().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
            TreeNode prev = null, curr = root;
            while (!stack.isEmpty() || curr != null) {
                while (curr != null) {
                    stack.push(curr);
                    // 左遍历
                    curr = curr.left;
                }
                // 吐出一个元素
                curr = stack.pop();
                if (prev == p) {
                    return curr;
                }
                prev = curr;
                curr = curr.right;
            }
            return null;
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
